package leetcode.dynamic;

import java.util.Arrays;
import java.util.List;


/*

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 */
public class LeetCode139_WordBreak {

    boolean flag = false;
    boolean done = false;
    public boolean wordBreak(String s, List<String> wordDict) {

        int[][] dp = new int[wordDict.size()][s.length()];
        int[][] isStart = new int[wordDict.size()][s.length()];

        for (int i = 0; i < wordDict.size(); i++){
            find(s, wordDict.get(i), i, dp, isStart);
        }

        int end = 0;
        search(wordDict, end, dp, isStart);

        return flag;
    }

    public void search(List<String> wordDict, int end, int[][] dp, int[][] isStart){

        if (end >= dp[0].length) return;
        int tempEnd;
        if (flag || done) return;

        int haveZero = 1;

        for (int i = 0; i < wordDict.size(); i++){
            if (end >= dp[0].length) return;

            tempEnd = end;

            if (dp[i][end] == 1){
                haveZero = 0;

                if (isStart[i][end] != 1) {
                    continue;
                }

                tempEnd += wordDict.get(i).length();

                if (tempEnd - 1 == dp[0].length - 1){
                    flag = true;
                    return;
                }
                search(wordDict, tempEnd, dp, isStart);
            }
        }

        if (haveZero == 1){
            done = true;
        }
    }

    public void find(String s, String s2, int i, int[][] dp, int[][] isStart){
        if (s2.length() > s.length()) return;

        int p, q = 0, tempQ;
        while (q < s.length()){
            p = 0;
            tempQ = q;
            while (p < s2.length() && tempQ < s.length()){
                if (s2.charAt(p) == s.charAt(tempQ)){
                    p++;
                    tempQ++;
                }else {
                    break;
                }
            }

            if (p == s2.length()){
                dp[i][q] = 1;
                dp[i][q + s2.length() - 1] = 1;

                isStart[i][q] = 1;
            }

            q++;
        }

    }

    public static void main(String[] args) {
//        String s = "leetcode";
//        List<String> wordDict = Arrays.asList("leet", "code");

//        String s = "aaaaaaa";
//        List<String> wordDict = Arrays.asList("aaaa", "aa");

//        String s = "ddadddbdddadd";
//        List<String> wordDict = Arrays.asList("dd","ad","da","b");
        //List<String> wordDict = Arrays.asList("a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa");
        //String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";


        String s = "cars";
        List<String> wordDict = Arrays.asList("car","ca","rs");
        boolean b = new LeetCode139_WordBreak().wordBreak(s, wordDict);

        System.out.println("b = " + b);
    }

}
